
\chapter{Módulo RISCO para o LLVM}
\label{c:risco_llvm}

O backend RISCO para o projeto LLVM é o módulo que permite o desenvolvimento de
software em uma linguagem de alto nível tendo como alvo o processador RISCO.
Como argumentado no capítulo \ref{c:sistemas_embarcados}, o uso de uma linguagem
de programação estruturada é imprescindível para o desenvolvimento moderno de
sistemas embarcados. Além disso, a existência deste suporte permite que o RISCO
se torne uma opção viável para o estudo de arquitetura de computadores e de
compiladores em geral. O sistema de instruções (\ref{s:risco_instrucoes})
desta plataforma, seguindo a filosofia RISC, é simples, conciso e completo. O
usuário final, utilizando o framework LLVM e o módulo RISCO, pode observar
todos os passos envolvidos na tradução do código original em linguagem de alto
nível para a linguagem de montagem do RISCO. 

Os motivos da escolha do LLVM para esta tarefa foram apresentados no capítulo
\ref{c:llvm}. Em teoria, como o backend RISCO habilita a tradução de código na
linguagem intermediária LLVM-IR para a sua linguagem de montagem, todas as
ferramentas descritas na arquitetura do LLVM da figura
\ref{fig:llvm_arquitetura} podem funcionar em uma plataforma RISCO. Na prática,
o suporte a estas ferramentas requer mais do que a implementação deste passo de
tradução, pois é preciso portar as ferramentas em si para a arquitetura
desejada. Neste trabalho procuramos criar somente o que foi necessário para a
compilação das linguagens de alto nível com um compilador estático, que não
inclui otimizações em tempo de execução \cite{llvm_main_art}. O foco principal
do backend RISCO é o suporte a compilação de programas nas linguagens C e C++.
Essas linguagens foram escolhidas pois, além de serem as linguagens que dominam
o desenvolvimento de sistemas embarcados \cite{es_architecture_guide}, são as
que tem o suporte mais estável no projeto LLVM \cite{llvm_site}. O compilador
Clang é capaz de gerar código LLVM-IR a partir de C e C++, e é utilizado na
ferramenta \texttt{risco-c}, que será descrita posteriormente.

A apresentação do projeto e desenvolvimento do backend RISCO se dá em 3 partes:
(i) decisões de projeto, (ii) especificação do backend e (iii) a etapa de
verificação do código gerado.


\section{Decisões de projeto}

A implementação do módulo RISCO para o LLVM envolveu algumas decisões de
projeto necessárias para o entendimento da arquitetura da solução, assim como
para a utilização correta da ferramenta. Antes de implementar os padrões de
tradução que serão abordados na seção \ref{s:especificacao_backend} é preciso
decidir, entre outras coisas, como será o processo de desenvolvimento, como o
módulo será utilizado pelo usuário final e quais instruções serão suportadas.

O módulo foi desenvolvido tendo como base os outros backends do LLVM cuja
plataforma alvo seja um processador da família RISC. Em particular, o código de
suporte ao MIPS e ao ARM, descritos por \citeonline{llvm_mips_arm}, foram de
importância significativa, pois estes dois conjuntos de instruções apresentam
várias semelhanças com relação às instruções RISCO. O backend RISCO é invocado
pelo usuário final utilizando um \emph{driver} do compilador.
\citeonline{asm_book} define um driver de compilador como sendo o programa que
se encarrega de coordenar a execução das diferentes ferramentas necessárias para
a compilação de um código em linguagem de alto nível até o binário executável
final. Geralmente estas ferramentas são o pré-processador C, o compilador, o
montador e o ligador. O driver ordena a execução de cada ferramenta e direciona
a sua saída para a próxima. Um exemplo de driver de compilador C em ambiente
Unix é o programa \texttt{gcc}, do projeto GCC \cite{gcc_site}.

Foi desenvolvido um driver de compilador próprio para o RISCO, denominado
\texttt{risco-c}. Trata-se de um script na linguagem Python \cite{python_book}
que executa os seguintes programas:

\begin{itemize}
  \item \texttt{clang}: Responsável por emitir um módulo LLVM-IR para cada
  unidade de compilação especificada na entrada do \texttt{risco-c}.
  
  \item \texttt{opt}: É a ferramenta do LLVM responsável por executar os passes
  de análise e otimização na representação intermediária do código. Ela é
  executada para cada módulo LLVM-IR, modificando o seu conteúdo. Segundo
  \cite{llvm_backend}, em 2009 o LLVM contava com 32 passes
  de análise e 63 passes de otimização. Os argumentos passados para o
  \texttt{opt} permitem especificar quais desses passes serão executados sob o
  código, levando em conta os objetivos finais. Por exemplo, o conjunto de
  passes executados pode ser diferente para uma compilação que tenta minimizar o
  tamanho final do código, com relação a outra que tenta maximizar a sua
  performance final. Alguns passes de otimização específicos ao backend RISCO
  também são executados nesta etapa. 
  
  \item \texttt{llc}: É o compilador da linguagem de representação
  intermediária, incluído com o LLVM. É responsável por ler o código em RI e
  gerar o código final em linguagem de montagem. O \texttt{risco-c} passa um
  argumento para o \texttt{llc} informando que o backend RISCO deverá ser
  utilizado.
  
  \item \texttt{risco-peep-opt}: A geração de código utilizando o backend RISCO
  ainda deixa algumas oportunidades de otimização \emph{peephole} no código
  final, como será explicado na seção \ref{s:especificacao_backend}. Este
  script foi desenvolvido para realizar pequenas modificações no código final
  em linguagem de montagem, antes da execução do montador.
  
  \item \texttt{risco-as}: Finalmente, o driver executa o montador/ligador
  discutido no capítulo \ref{c:plataforma_base}. Ele recebe como entrada os
  arquivos em linguagem de montagem de todas as unidades de compilação e gera o
  binário executável final, que pode ser passado ao simulador \texttt{risco-sim}
  posteriormente.
\end{itemize}

Tanto o backend RISCO como os scripts que o auxiliam foram desenvolvidos com
uma variação do processo de desenvolvimento dirigido a testes, como descrito em
\cite{tdd_art}. Ele é apresentado em mais detalhes na seção
\ref{s:verificacao_codigo}. O \texttt{risco-c} facilita o processo de
verificação do compilador fazendo com que só seja necessário um comando para a
execução do processo de compilação. 

Nas próximas seções serão discutidas as decisões de projeto relacionadas ao
código que será gerado pelo backend RISCO.


\subsection{Suporte às funcionalidades da LLVM-IR}

A linguagem de representação intermediária do projeto LLVM, como descrita em
\ref{s:llvm_ir}, contêm diversas funcionalidades que não são diretamente
relevantes para a plataforma RISCO ou que não podem ser mapeadas para ela.
Dessa maneira, o módulo RISCO dá suporte a um subconjunto dessas
funcionalidades, diminuindo a complexidade da sua implementação.

Com relação aos atributos de um módulo LLVM-IR, o backend RISCO atualmente
ignora os diferentes tipos de ligação de símbolos que não sejam \emph{private}
, \emph{global} ou \emph{extern}. Entre esses, estão: \emph{linkonce},
\emph{weak}, \emph{appending} e \emph{weak\_odr}. Estes atributos são
funcionalidades avançadas dos ligadores, servindo para a implementação eficiente
de algumas construções de linguagens de programação avançadas, como os templates
do C++ \cite{linkers_loaders}. Além destes, os atributos que contêm as
informações de depuração do programa, em forma de metadados da LLVM-IR, também
são ignorados pois a plataforma RISCO ainda não conta com o suporte de um
depurador. 

A maioria das instruções da RI é suportada, com as seguintes exceções:

\begin{itemize}
  \item As instruções com ponto flutuante não podem ser facilmente sintetizadas
  para a plataforma RISCO pois não há suporte a este tipo de dados no
  processador. Portanto, a sua utilização causa um  erro em tempo de
  compilação.
  
  \item A LLVM-IR introduziu o conceito de \emph{funções intrínsecas}
  \cite{llvm_llva} para representar instruções complexas da arquitetura base,
  tais como manipulação avançada de bits, funções trigonométricas, operações
  atômicas na memória principal e suporte a listas variáveis de argumentos nas
  subrotinas. O módulo RISCO não dá suporte a estas instruções.
  
  \item As instruções de multiplicação, divisão e resto são suportadas
  indiretamente pelo backend RISCO, utilizando implementações em  software. Foi
  criado um passe de transformação de código para o LLVM,  denominado
  \texttt{MulDivTransform}, que identifica estas operações no código
  intermediário e as transforma em chamadas para as suas respectivas funções. 
  As funções tem complexidade de pior caso $O(1)$ com relação aos valores dos
  parâmetros e complexidade $O(n^2)$ com relação ao número de bits dos 
  parâmetros. Em geral, elas são eficientes o bastante para uso geral, porém 
  ineficientes para aplicações numéricas.
\end{itemize}


\subsection{Interface binária}
\label{ss:risco32}

Antes de começar a implementação de um compilador para uma nova arquitetura é
preciso decidir como será a ``organização'' do programa em tempo de execução, e
como ele utiliza cada um dos registradores da arquitetura. A organização do
programa diz respeito a como ele utiliza a região de memória denominada de
\emph{pilha} para manter os \emph{registros de ativação} \cite{dragon_book} das
rotinas sendo executadas. Já o uso dos registradores indica qual o protocolo
de utilização dos registradores quando diversas funções executam sob a mesma
área de memória. Estas duas convenções são comumente denominadas de
\emph{convenção de chamada} \cite{patterson_book} da plataforma. O processador
em si é independente da convenção de chamada utilizada, porém a definição dela
se faz necessária para a geração automática de código que possa ser reutilizado
em outra compilação. Por exemplo, o código de uma biblioteca necessita utilizar
a mesma convenção do código que utiliza a biblioteca. Caso contrário, haverá
uma incompatibilidade entre os binários e o código gerado não será correto.

A convenção de chamada descrita nesta seção é específica para sistemas de 32
bits, e foi nomeada \emph{RISCO32}. Na prática, as arquiteturas RISC em geral
utilizam convenções de chamada semelhantes \cite{linkers_loaders}. A principal
exceção é a arquitetura SparcV8, cujo conceito de janela de registradores 
\cite{sparcv8} influencia a convenção. A RISCO32 é baseada na convenção
utilizada pela arquitetura MIPS \cite{llvm_mips_arm}, com adaptações para lidar
com diferenças nos registradores e na instrução de chamada de subrotinas.

Uma convenção de chamada dita regras para as instruções que serão geradas em
4 pontos do código. Assumindo que uma função pai \texttt{F} quer chamar a
subrotina \texttt{G}, a convenção atuaria em \cite{patterson_book}: (1) antes
de \texttt{F} executar a instrução de chamada da subrotina; (2) no início da
execução de \texttt{G}; (3) antes que \texttt{G} execute uma instrução de
retorno; (4) assim que a função \texttt{F} reinicia a sua execução. A convenção
de chamada divide o conjunto de registradores em 2 classes:

\begin{itemize}
  \item Salvo pela rotina pai (do inglês \emph{caller-saved}): são
  registradores de características temporária, geralmente sobrescritos pela
  rotina que será chamada. Caso a rotina pai queira preservar o valor dos
  registradores para utilizá-los após a chamada, ela deve salvá-los na pilha e
  recuperá-los após a chamada.
  
  \item Salvo pela rotina chamada (do inglês \emph{callee-saved}): são
  registradores de característica persistente, cujos valores devem se manter ao
  longo das chamadas de subrotinas. Caso uma rotina queira escrever em um
  registrador deste tipo, ela deve primeiramente salvar o seu valor antigo na
  pilha, e recuperá-lo antes de retornar para a rotina pai.
\end{itemize}

Os registradores da plataforma RISCO foram classificados nestas duas classes,
conforme a tabela \ref{tab:convencao_registradores}. A tabela também informa
quais são os identificadores utilizados para referenciar os registradores na
linguagem de montagem. 

\begin{table}[htb]
\begin{center}
\begin{tabular}{ c | c | c | c }
  \textbf{Nome no risco-as} & \textbf{Código} & \textbf{Classe} &
  \textbf{Comentário} \\
  \hline
  
  \texttt{\$zero} & R00 & (N/A) & Sempre guarda 0 \\
  \texttt{\$psw} & R01 & caller-saved & Palavra de status \\
  \texttt{\$v0} & R02 & caller-saved & Valor de retorno de uma subrotina \\
  \texttt{\$a0 - \$a4} & R03 - R07 & caller-saved & Argumentos da rotina \\
  \texttt{\$t0 - \$t9} & R08 - R17 & caller-saved & Propósito geral \\
  \texttt{\$s0 - \$s7} & R18 - R25 & callee-saved & Propósito geral \\
  (N/A) & R26 - R28 & (N/A) & Reservados \\
  \texttt{\$fp} & R29 & callee-saved & Ponteiro do registro \\
  \texttt{\$pc} & R31 & (N/A) & Contador do programa \\
\end{tabular}
\end{center}
\caption{Convenções de uso para os registradores RISCO
         \label{tab:convencao_registradores}}
\end{table}

A convenção de chamada é detalhada a seguir. Em cada passo, o número entre
colchetes indica qual dos 4 pontos do código mencionados anteriormente está
sendo referenciado no momento. Para um melhor entendimento da convenção é
necessário conhecimento sobre o conceito de registro de ativação de uma rotina
\cite{dragon_book}. 

\begin{itemize}
  \item {[1]} Na subrotina pai, cada registrador caller-saved cujo valor será
  necessário após a chamada da subrotina filha deve ser salvo na pilha, em
  qualquer ordem.
  
  \item {[1]} Os 5 primeiros argumentos da subrotina são postos nos
  registradores  \texttt{\$a0} a \texttt{\$a4}. Os argumentos que não cabem em
  um registrador e os demais que  não foram para os registradores são postos na
  pilha, na ordem em que foram  declarados.
  
  \item {[2]} Ao iniciar a sua execução, a subrotina primeiramente reserva a
  memória na pilha com o tamanho do seu registro de ativação. A pilha cresce
  dos valores mais  altos para os mais baixos, e o espaço é alocado
  decrementando o registrador \texttt{\$sp}. Ela também salva o antigo valor do
  registrador \texttt{\$fp} e guarda nele a posição da pilha onde se inicia o
  registro de ativação da subrotina atual.
  
  \item {[2]} A subrotina chamada salva na pilha os registradores callee-saved
  que terá que usar posteriormente. Além disso, ela utiliza o espaço do seu
  registro na pilha para guardar as suas variáveis locais, caso seja necessário.
  
  \item {[3]} Após a execução da subrotina chamada, ela salva o valor que será
  retornado a subrotina pai no registrador \texttt{\$v0}. Caso o valor não
  caiba em um registrador, ele é retornado na pilha.
  
  \item {[3]} Antes de executar a instrução de retorno, a subrotina chamada
  também recupera os registradores callee-saved que foram salvos anteriormente.
  
  \item {[4]} A subrotina pai recupera o valor dos registradores caller-saved
  que foram salvos na pilha.
\end{itemize}

\begin{figure}[htb]
  \centering
  \includegraphics[scale=0.7]{images/stack-frame}
  \textsf{\caption{Registro de ativação de uma rotina na convenção RISCO32
          \label{fig:stack_frame}}}
\end{figure}

A figura \ref{fig:stack_frame} representa o estado da pilha no momento da
execução de uma subrotina chamada por uma rotina pai, como nos exemplos dados
acima. Note que, realizando um acesso a pilha com endereçamento indireto tendo
como base o registrador \texttt{\$fp}, é possível acessar os argumentos e as
variáveis locais com deslocamentos fixos, facilitando a geração de código pelo
compilador.


\section{Especificação do backend}
\label{s:especificacao_backend}

Com a definição dos detalhes da interface binária RISCO32 pronta, foi possível
a implementação do módulo RISCO para o LLVM. Como visto em \ref{s:llvm_codegen},
um \emph{backend} LLVM é uma biblioteca dinâmica contendo classes que
implementam interfaces abstratas, utilizadas pela parte do gerador de código que
é independente da arquitetura alvo \cite{llvm_backend}. O gerador utiliza estas
classes para descobrir as características específicas da arquitetura,
utilizando-as durante os algoritmos de geração de código. Dessa maneira, tais
algoritmos são genéricos o bastante para serem reutilizados em todas as
arquiteturas alvo do LLVM \cite{llvm_main_art}. Detalhes sobre os componentes do
módulo são descritos nas seções \ref{ss:targetmachine} a \ref{ss:mcasminfo}.

\subsection{TargetMachine}
\label{ss:targetmachine}

O componente \texttt{RISCOTargetMachine} implementa a interface
\texttt{LLVMTargetMachine} e é o ponto de principal de comunicação entre o
framework de geração de código e o módulo RISCO. Além de conter métodos de
acesso para todos os outros componentes do módulo, ele tem as seguintes
funcionalidades:

\begin{itemize}
  \item O \texttt{TargetMachine} informa ao gerador de código como os dados são
  representados na arquitetura. Isto inclui tamanho da palavra, alinhamento
  dos bytes na memória e tamanho de um ponteiro. Para o RISCO, todos os dados
  são representados em 4 bytes, organizados na memória com a codificação
  \emph{little-endian}.
  
  \item Este componente pode informar ao framework LLVM que existem diferentes
  versões do processador, cada qual com algumas funcionalidades presentes ou
  omitidas. Para o RISCO, só foi informado um modelo do processador, o que foi
  descrito no \mbox{capítulo \ref{c:risco}}.
  
  \item Finalmente, é neste componente que o módulo RISCO é registrado no
  framework LLVM. Após o passo de registração, o módulo se torna visível nas
  ferramentas de geração de código (como o \texttt{llc}).
\end{itemize}

\subsection{RegisterInfo e CallingConv}

Estes componentes são responsáveis pela descrição do conjunto de registradores
da plataforma alvo, junto com as suas propriedades, e as convenções de chamada
que são suportadas. Juntas, elas informam ao gerador de código as principais
características da interface binária RISCO32.

Os registradores podem ser divididos em classes de acordo com o tipo de dados
que eles guardam. No RISCO, todos são da mesma classe (guardam sempre uma
palavra inteira). Também é possível especificar o conceito de sub-registradores,
existentes, por exemplo, nos processadores X86 \cite{x86_processor}, e
informações de depuração associadas a registradores. Estas funcionalidades não
foram necessárias para a especificação dos registradores RISCO. Devido a alta
repetição de informações na especificação de cada registrador, o código para a
classe \texttt{RISCORegisterInfo} é gerado automaticamente a partir de uma
especificação \emph{TablenGen}, como foi visto em \ref{ss:llvm_descricao_alvo}.
O exemplo \ref{alg:tablegen_registerinfo} mostra um trecho simplificado da
especificação TableGen \texttt{RISCORegisterInfo}.

\begin{algorithm}[htb]
  \centering
\begin{verbatim}

    class RiscoReg<bits<5> num, string n> : Register<n> {
      field bits<5> Num;
      let Num = num;
    }
    let Namespace = "Risco" in {
      ...
      def A0   : RiscoReg< 4, "$a0">;
      def A1   : RiscoReg< 5, "$a1">;
      def A2   : RiscoReg< 6, "$a2">;
      def A3   : RiscoReg< 7, "$a3">;
      ...
    }
\end{verbatim}
\textsf{\caption{Trecho simplificado da especificação dos registradores RISCO
          \label{alg:tablegen_registerinfo}}}
\end{algorithm}

A especificação da convenção de chamada inicialmente era feita utilizando
código C++ escrito a mão, descrevendo as regras da convenção \cite{llvm_site}.
Recentemente, foi implementado o suporte à geração automática do módulo C++ a
partir de uma especificação TableGen, assim como o \texttt{RegisterInfo}. A
figura \ref{alg:tablegen_callingconv} mostra um trecho da especificação para o
RISCO32. A classe \texttt{CallingConv} consiste de uma lista de ações que são
analisadas em ordem para cada argumento ou valor de retorno de uma subrotina. O
registro \texttt{RetCC\_RISCO32} descreve a convenção para os valores de
retorno, e o \texttt{CC\_RISCO32} descreve a convenção para a chamada de
subrotina com argumentos.

\begin{algorithm}[htb]
  \centering
\begin{verbatim}

    def RetCC_RISCO32 : CallingConv<[
      CCIfType<[i32], CCAssignToReg<[V0]>>,
      CCAssignToStack<4, 4>
    ]>;

    def CC_RISCO32 : CallingConv<[
      CCIfType<[i8, i16], CCPromoteToType<i32>>,
      CCIfType<[i32], CCAssignToReg<[A0, A1, A2, A3, A4]>>,
      CCAssignToStack<4, 4>
    ]>;
\end{verbatim}
\textsf{\caption{Trecho da especificação da convenção de chamada RISCO32
          \label{alg:tablegen_callingconv}}}
\end{algorithm}

\subsection{TargetLowering}

Este é o componente inicial na etapa de seleção de instruções. De acordo com o
processo apresentado na seção \ref{ss:llvm_instruction_selection}, a seleção de
instruções se dá sobre um grafo direcionado acíclico denominado
\emph{SelectionDAG}. A etapa de seleção em si transforma o SelectionDAG em
outro grafo ``legalizado'', que utiliza somente operações e tipos de dados
presentes na arquitetura alvo. Entretanto, antes da execução do algoritmo de
seleção, o SelectionDAG original (criado a partir do código em LLVM-IR) tem
alguns nós substituídos por nós específicos do backend. A introdução destes nós
simplifica a especificação dos padrões de reescrita de instruções, que serão
discutidos na seção \ref{ss:risco_llvm_instrinfo}.

Apenas parte dos nós específicos utilizados são obrigatórios, sendo estes:
\texttt{JmpCall}, representando uma chamada de subrotina, e \texttt{Ret},
representando o retorno. Os nós opcionais escolhidos foram \texttt{Hi} e
\texttt{Lo}. São nós de operação, representando a obtenção dos 16 bits mais ou
menos significativos, respectivamente, de um número. A introdução destes nós
facilitou o desenvolvimento dos padrões de reescrita para as instruções com
formato 4 (seção \ref{s:risco_instrucoes}).

\subsection{InstrInfo}
\label{ss:risco_llvm_instrinfo}

O componente \texttt{RISCOInstrInfo} contêm a especificação de todas as
instruções que o LLVM pode utilizar na emissão de código para a plataforma
RISCO, junto com algumas propriedades e os seus padrões de seleção.

É interessante notar que não existe uma bijeção entre o conjunto de instruções
RISCO que foram especificadas no backend LLVM e o conjunto de instruções reais
da plataforma, apresentadas no apêndice \ref{c:apendice_instrucoes}. Este fato
está relacionado com uma diferença na organização do conjunto de instruções do
RISCO com o das outras arquiteturas RISC comuns, como o MIPS \cite{mips32}. Na
codificação de uma instrução RISCO há uma separação física e semântica entre a
definição da instrução e a definição dos seus operandos \cite{risco_tese}.
Esta separação faz com que seja possível utilizar qualquer combinação de
\mbox{instrução $\times$ operandos}, dentre os 5 formatos de operandos
existentes. Pode-se dizer que as instruções RISCO apresentam um tipo de
\emph{polimorfismo} básico pois são independentes dos tipos dos seus operandos.
Como discutido na seção \ref{s:risco_instrucoes}, algumas destas combinações
geram instruções que não apresentam aplicação prática.

O impacto desta característica na implementação do módulo RISCO é que grande
parte das instruções reais deve ser mapeada para no mínimo duas instruções no
backend LLVM: uma versão com dois operandos em registradores e outra com um
operando em registrador e outro operando imediato (constante). Por exemplo, a
instrução \texttt{add} aparece no componente \texttt{RISCOInstrInfo} como
\texttt{ADDrr} e \texttt{ADDri}. Estas duas formas cobrem as instruções com
formato 1 e 2. Os formatos 3 e 5 são identificados pelo montador
\texttt{risco-as}, que é capaz de analisar os operandos da instrução e
determinar a codificação mais adequada para cada caso. As instruções de formato
4 são um caso especial, descrito mais adiante nesta seção.

A especificação de uma instrução em um backend LLVM consiste de: nome da
instrução; um template, em forma de string, para a geração de código em
linguagem de montagem, especificando como a instrução e os seus operandos devem
ser impressos no arquivo final; especificação do nó que representa a instrução
no SelectionDAG incluindo, por exemplo, o número de arestas de saída para
operandos e de entrada para os seus resultados; e por fim o padrão de
reescrita, que especifica qual parte do grafo SelectionDAG original pode ser
substituído por esse nó. Todo o código C++ equivalente a definição das
instruções é gerado automaticamente a partir de uma especificação TableGen
contendo estas informações. 

\begin{algorithm}[htb]
  \centering
\begin{verbatim}

   let isCommutable = 1 in
   class ArithR<bits<6> op, bits<6> func, string instr_asm, SDNode OpNode>:
     FR< op, func, (outs CPURegs:$dst), (ins CPURegs:$b, CPURegs:$c),
         instr_asm,
         [(set CPURegs:$dst, (OpNode CPURegs:$b, CPURegs:$c))]>;
      
   def ADDrr : ArithR<0x00, 0x00, "add $dst, $b, $c", add>;
\end{verbatim}
\textsf{\caption{Especificação da instrução \texttt{ADDrr} no backend RISCO
          \label{alg:exemplo_instrinfo}}}
\end{algorithm}

Primeiramente, são definidas classes TableGen para cada tipo de instrução e
tipo de operandos. Por exemplo: uma classe para instruções aritmético-lógicas
com dois operandos em registradores. Em seguida, cada instrução é definida por
um registro que instancia a sua respectiva classe, preenchendo os valores
necessários. O padrão de reescrita é definido em dois passos. Parte dele é
comum a todas as instruções de uma certa classe e pode ser definido na própria
classe. A parte que é particular a cada instrução é passada como parâmetro de
instanciação da classe. Observe o exemplo \ref{alg:exemplo_instrinfo} para a
definição da instrução \texttt{ADDrr}. O padrão de reescrita é
\texttt{(set CPURegs:\$dst, (OpNode CPURegs:\$b, CPURegs:\$c))}, onde
\texttt{OpNode} é instanciado com a operação \texttt{add} na instanciação do
registro. Desta maneira, quando o seletor de instruções encontra este padrão no
grafo SelectionDAG (uma adição entre dois registradores, com o resultado sendo
escrito em outro registrador) ele poderá substituí-lo por uma instrução
\texttt{ADDrr}. A string \texttt{``add \$dst, \$b, \$c''} é o template
utilizado para imprimir a instrução no código em linguagem de montagem.

\begin{algorithm}[htb]
\centering
\begin{verbatim}

        def SLT     : SetCC_R<0x00, 0x2a,
          "cmp ($b, $c)\n\t"
          "and $dst, $$psw, LT_MASK\n\t"
          "srl $dst, $dst, LT_POS",
          setlt>;
      
        def LB      : LoadM<0x20,
          "ld $dst, $addr\n\t"
          "sll $dst, $dst, 24\n\t"
          "sra $dst, $dst, 24",
          sextloadi8>;
      
        def BEQ     : CBranch<0x04,
          "cmp ($a, $b)\n\t"
          "jmpeq $offset",
          seteq>;
\end{verbatim}
\textsf{\caption{Exemplos de instruções compostas na especificação
        \texttt{RISCOInstrInfo} \label{alg:exemplo2_instrinfo}}}
\end{algorithm}

A maior parte das instruções definidas tem correspondentes diretos na LLVM-IR,
como o caso da instrução de adição. Entretanto, outras tem que ser modeladas
como uma sequência de instruções RISCO. O exemplo \ref{alg:exemplo2_instrinfo}
mostra 3 instruções com esta característica.

\begin{itemize}
  \item \texttt{SLT}: É o padrão de reescrita para o nó \texttt{setlt} do
  SelectionDAG. A operação significa: \texttt{\$dst} recebe 1 caso \texttt{\$b}
  $<$ \texttt{\$c}, caso contrário recebe 0. Com instruções RISCO, é preciso
  comparar os dois números e realizar duas operações aritméticas para conseguir
  o mesmo resultado, como mostrado no exemplo.
  
  \item \texttt{LB}: É o padrão relativo ao nó \texttt{sextloadi8} do
  SelectionDAG, e trata-se de carregar um 1 byte da memória para um registrador,
  preservando sinal. Como no RISCO o acesso a memória só é possível para
  recuperar uma palavra inteira, é preciso carregar uma palavra e calcular o
  byte requisitado manualmente.
  
  \item \texttt{BEQ}: Especifica a operação de salto com a condição de
  igualdade entre dois operandos. No RISCO, são necessárias duas instruções:
  uma para a comparação e outra para o salto. 
\end{itemize}

\begin{algorithm}[htb]
\centering
\begin{verbatim}

       def : Pat<(i32 imm:$imm),
                 (ORi (LUi (HI16 imm:$imm)), (LO16 imm:$imm))>;
\end{verbatim}
\textsf{\caption{Padrão de reescrita para o suporte a constantes de 32 bits
          \label{alg:exemplo3_instrinfo}}}
\end{algorithm}

A última seção da especificação contêm padrões de reescrita mais genéricos, que
não correspondem a uma só instrução. Por exemplo, para carregar uma constante
de 32 bits em um registrador com o RISCO são necessárias duas instruções: uma
para carregar a parte mais significativa (instrução de formato 4) e outra para
somar o resultado com a parte menos significativa. O padrão que especifica esta
técnica é descrito no exemplo \ref{alg:exemplo3_instrinfo}.

\subsection{MCAsmInfo}
\label{ss:mcasminfo}

O módulo \texttt{RISCOMCAsmInfo} é responsável por informar os elementos
sintáticos da linguagem de montagem RISCO para o gerador de código. Por
exemplo, as diretivas do montador apresentadas na subseção
\ref{ss:assembly_risco}. Na impressão de cada instrução, o template contido na
sua especificação TableGen tem os seus parâmetros preenchidos com os operandos
da instrução antes de ser impresso no arquivo final. Este é o último componente
do módulo RISCO. Os exemplos abaixo mostram o resultado de um processo de
tradução para a linguagem de montagem do RISCO. O código
\ref{alg:exemplo_traducao_c} contêm o código original em C e o código
\ref{alg:exemplo_traducao_risco} apresenta o código de montagem equivalente.

\begin{algorithm}[htb]
\centering
\begin{verbatim}

#include "risco/cstdlib.h"

int main(void) {
  int a = read_int();
  int b = a + 1;
  print_int(b);
  return 0;
}
\end{verbatim}
\textsf{\caption{Exemplo de compilação de código para o RISCO: código em C
          \label{alg:exemplo_traducao_c}}}
\end{algorithm}

\begin{algorithm}[htb]
\centering
\begin{verbatim}

#include "risco/ext.h"
#include "risco/stdlib.h"
        .global main
        .text
main:
        add $sp, $sp, -24
        st [$sp + 20], $ra
        sr read_int
        nop
        add $a0, $v0, 1
        sr print_int
        nop
        add $v0, $zero, 0
        ld $ra, [$sp + 20]
        nop
        add $sp, $sp, 24
        ret
        nop
\end{verbatim}
\textsf{\caption{Exemplo de compilação de código para o RISCO: código na
        linguagem de montagem do RISCO \label{alg:exemplo_traducao_risco}}}
\end{algorithm}
  
É possível observar no código os aspectos da convenção RISCO32 discutidos
anteriormente, assim como o uso de funções da biblioteca padrão que encapsulam
as chamadas de sistema específicas do simulador \texttt{risco-sim}
(subseção \ref{ss:risco_sim_syscalls}).


\section{Verificação do compilador}
\label{s:verificacao_codigo}

O processo de desenvolvimento de um compilador requer técnicas e cuidados
específicos devido a complexidade inerente a esta classe de softwares.
\citeonline{dragon_book} e \citeonline{compilers_appel} comentam que os
algoritmos complexos utilizados e as relações internas entre os seus
módulos fazem com que as tarefas de construção e manutenção de um compilador
sejam difíceis. Como o código de entrada, em linguagem de alto nível, é
transformado sucessivamente de acordo com os diferentes passes de otimização em
um compilador moderno, um erro no código gerado não é facilmente rastreado para
um erro no código do tradutor. Por esses motivos, o projetista de um compilador
deve adaptar técnicas modernas e eficientes de testes para garantir um bom
nível de confiança no produto final. Trabalhos recentes na área de testes de
compiladores \cite{comp_test_1, comp_test_2} mostram uma tendência
clara com relação à utilização de diferentes técnicas para geração automática de
casos de teste. 

\abrv[DDT -- Desenvolvimento Dirigido a Testes]

Para a construção do módulo RISCO para o LLVM não foram utilizados testes
automatizados pois estes são guiados para implementações mais maduras, onde
testam funcionalidades avançadas do compilador. Nesse contexto, casos de
teste mais simples, criados manualmente, seriam mais efetivos para garantir o
funcionamento básico do compilador. Com relação à metodologia, tanto o backend
RISCO como os scripts que o auxiliam foram desenvolvidos utilizando uma variação
do processo de desenvolvimento dirigido a testes (DDT), como descrito em
\cite{tdd_art}. Na prática, não houve a atenção necessária para o rigor dos
testes de unidades que é comum no desenvolvimento baseado em DDT. O foco do
processo esteve na execução de testes de regressão a cada modificação do módulo,
com o seguinte esquema:

\begin{enumerate}
  \item Um conjunto de programas de teste é criado. Inicialmente, um programa
  em C contendo o mínimo possível de código para ser compilado com sucesso é
  adicionado no conjunto.
  
  \item O processo de compilação é executado para todos os programas do
  conjunto de testes.
  
  \item Caso uma das compilações resulte em um erro interno do compilador, o
  erro é consertado e o processo é reiniciado do passo 2.
  
  \item Todos os programas de teste são executados. Cada programa tem um arquivo
  de texto contendo uma entrada  pré-definida e um outro arquivo contendo a
  saída esperada\footnote{A saída  esperada para uma certa entrada de um
  programa poderia ser determinada manualmente. Entretanto, para obter mais
  confiança no processo, a saída é criada a partir da execução de uma outra
  versão do mesmo programa, compilada com o GCC.}.
  
  \item Caso um dos programas apresente um saída diferente da esperada, o
  compilador gera código incorreto para o exemplo. O erro é consertado e o
  processo é reiniciado do passo 2.
  
  \item Caso todos os programas passem nos testes, existem duas opções: É
  possível realizar modificações para adicionar complexidade em um dos testes
  existentes ou então um novo programa de teste é criado e adicionado no
  conjunto.
  
  \item O processo é repetido indefinidamente, voltando ao passo 2.
\end{enumerate}

O processo utilizado ajudou a encontrar defeitos no código do compilador que
resultavam na geração de código incorreto. Com o passar do tempo houve uma
estabilização e todos os testes que foram adicionados a partir deste momento
compilavam com sucesso, com algumas exceções. Foi criado um repositório
alternativo com alguns casos de teste que ainda não são compilados corretamente
para que os defeitos sejam consertados no futuro. O uso do simulador
\texttt{risco-sim} foi imprescindível no processo de testes do compilador pois
ele permite agilidade e flexibilidade na execução dos programas compilados com o
módulo RISCO. Além disso, as chamadas de sistema definidas pelo simulador
permitiram a criação de programas com características mais práticas do que
programas de teste mais simples, sem interação com a plataforma hospedeira
(\emph{host}). 

\begin{algorithm}[htb]
\centering
\begin{verbatim}

#include "risco/iostream.hpp"
#include "risco/stl.hpp"
using namespace std;

char keyboard [47] = {
  char(96),'1','2','3','4','5','6','7','8','9','0','-','=',
  'Q','W','E','R','T','Y','U','I','O','P','[',']','\\',
  'A','S','D','F','G','H','J','K','L',';',char(39),
  'Z','X','C','V','B','N','M',',','.','/' 
}, line[500];

int main(void) {
  while (cin >> line && strcmp(line, "#")) {
    int line_len = strlen(line);
    for (int i = 0; i < line_len; i++) {
      for (int j = 0; j < 47; j++) {
        if (line[i] == keyboard[j]) {
          line[i] = keyboard[j-1];
          break;
        }
      }
    }
    cout << line << endl;
  }
  return 0;
}
\end{verbatim}
\textsf{\caption{Programa teste do compilador \texttt{risco-c} em C++
        \label{alg:caso_teste}}}
\end{algorithm}

A utilização da biblioteca padrão pode ser observada no exemplo
\ref{alg:caso_teste}. Para facilitar a escrita dos programas teste, foi
desenvolvida uma pequena interface para as chamadas de sistema do simulador que
imita a biblioteca padrão do C++ com relação a utilização dos objetos
\texttt{cin} e \texttt{cout} \cite{c++}. Além disso, algumas funções e
estruturas de dados básicas foram incluídas no arquivo \texttt{risco/stl.hpp}. O
conjunto de testes utilizado consiste de 43 programas em C e C++, dos quais 35
são soluções para problemas utilizados em competições de programação,
cujos enunciados são disponibilizados publicamente pela Universidad de
Valladolid na página \cite{uva}. Os arquivos com as soluções já existiam
previamente e só foram adaptados para utilizar a biblioteca padrão provida pelo
compilador RISCO.

Este capítulo encerra a apresentação do módulo RISCO para o LLVM. O capítulo
\ref{c:analise_codigo} discute as análises realizadas sob o código gerado por
este backend.
